﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace Net.System
{
    /// <summary>
    /// List类, 添加是有序的, 移除是无序的,极速的
    /// </summary>
    /// <typeparam name="T"></typeparam>
    [DebuggerTypeProxy(typeof(Mscorlib_CollectionDebugView<>))]
    [DebuggerDisplay("Count = {Count}")]
    [Serializable]
    public class FastList<T> : IList<T>, ICollection<T>, IEnumerable<T>, IEnumerable, IList, ICollection, IReadOnlyList<T>, IReadOnlyCollection<T>
    {
        // 字段
        public T[] Items;
        public int _size;
        [NonSerialized]
        private readonly object _syncRoot = new();
        private static readonly T[] _emptyArray = new T[0];

        // 属性
        public int Capacity
        {
            get => Items.Length;
            set
            {
                if (value == Items.Length)
                    return;
                if (value > 0)
                {
                    T[] array = new T[value];
                    if (_size > 0)
                    {
                        Array.Copy(Items, 0, array, 0, _size);
                    }
                    Items = array;
                    return;
                }
                Items = _emptyArray;
            }
        }

        public int Count => _size;

        bool IList.IsFixedSize => false;

        bool ICollection<T>.IsReadOnly => false;

        bool IList.IsReadOnly => false;

        bool ICollection.IsSynchronized => false;

        public object SyncRoot => _syncRoot;

        public T this[int index]
        {
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get => Items[index];
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set => Items[index] = value;
        }

        object IList.this[int index]
        {
            get => this[index];
            set => this[index] = (T)value;
        }

        public FastList()
        {
            Items = _emptyArray;
        }

        public FastList(int capacity)
        {
            if (capacity == 0)
            {
                Items = _emptyArray;
                return;
            }
            Items = new T[capacity];
        }

        public FastList(IEnumerable<T> collection)
        {
            if (collection is not ICollection<T> collection2)
            {
                _size = 0;
                Items = _emptyArray;
                foreach (T item in collection)
                {
                    Add(item);
                }
                return;
            }
            int count = collection2.Count;
            if (count == 0)
            {
                Items = _emptyArray;
                return;
            }
            Items = new T[count];
            collection2.CopyTo(Items, 0);
            _size = count;
        }

        private static bool IsCompatibleObject(object value)
        {
            return value is T || (value == null && default(T) == null);
        }

        public virtual void Add(T item)
        {
            Add(item, out _);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public virtual void Add(T item, out int index)
        {
            index = _size;
            if (index == Items.Length)
                EnsureCapacity(index + 1);
            Items[index] = item;
            _size++;
        }

        int IList.Add(object item)
        {
            Add((T)item);
            return Count - 1;
        }

        public virtual void AddRange(IEnumerable<T> collection)
        {
            InsertRange(_size, collection);
        }

        public ReadOnlyCollection<T> AsReadOnly()
        {
            return new ReadOnlyCollection<T>(this);
        }

        public virtual int BinarySearch(int index, int count, T item, IComparer<T> comparer)
        {
            if (index < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (count < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (_size - index < count)
            {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
            }
            return Array.BinarySearch(Items, index, count, item, comparer);
        }

        public int BinarySearch(T item)
        {
            return BinarySearch(0, Count, item, null);
        }

        public int BinarySearch(T item, IComparer<T> comparer)
        {
            return BinarySearch(0, Count, item, comparer);
        }

        public virtual void Clear()
        {
            if (_size > 0)
            {
                Array.Clear(Items, 0, _size);
                _size = 0;
            }
        }

        public virtual void ClearSize()
        {
            _size = 0;
        }

        public bool Contains(T item)
        {
            if (item == null)
            {
                for (int i = 0; i < _size; i++)
                {
                    if (Items[i] == null)
                    {
                        return true;
                    }
                }
                return false;
            }
            var @default = EqualityComparer<T>.Default;
            for (int j = 0; j < _size; j++)
            {
                if (@default.Equals(Items[j], item))
                {
                    return true;
                }
            }
            return false;
        }

        bool IList.Contains(object item)
        {
            return IsCompatibleObject(item) && Contains((T)item);
        }

        public FastList<TOutput> ConvertAll<TOutput>(Converter<T, TOutput> converter)
        {
            if (converter == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter);
            }
            var list = new FastList<TOutput>(_size);
            for (int i = 0; i < _size; i++)
            {
                list.Items[i] = converter(Items[i]);
            }
            list._size = _size;
            return list;
        }

        public virtual void CopyTo(T[] array)
        {
            CopyTo(array, 0);
        }

        void ICollection.CopyTo(Array array, int arrayIndex)
        {
            if (array != null && array.Rank != 1)
            {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
            }
            try
            {
                Array.Copy(Items, 0, array, arrayIndex, _size);
            }
            catch (ArrayTypeMismatchException)
            {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType);
            }
        }

        public virtual void CopyTo(int index, T[] array, int arrayIndex, int count)
        {
            if (_size - index < count)
            {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
            }
            Array.Copy(Items, index, array, arrayIndex, count);
        }


        public virtual void CopyTo(T[] array, int arrayIndex)
        {
            Array.Copy(Items, 0, array, arrayIndex, _size);
        }

        private void EnsureCapacity(int min)
        {
            if (Items.Length < min)
            {
                int num = (Items.Length == 0) ? 4 : (Items.Length * 2);
                if (num > 2146435071)
                {
                    num = 2146435071;
                }
                if (num < min)
                {
                    num = min;
                }
                Capacity = num;
            }
        }


        public bool Exists(Predicate<T> match)
        {
            return FindIndex(match) != -1;
        }


        public T Find(Predicate<T> match)
        {
            if (match == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            for (int i = 0; i < _size; i++)
            {
                if (match(Items[i]))
                {
                    return Items[i];
                }
            }
            return default;
        }


        public List<T> FindAll(Predicate<T> match)
        {
            if (match == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            var list = new List<T>();
            for (int i = 0; i < _size; i++)
            {
                if (match(Items[i]))
                {
                    list.Add(Items[i]);
                }
            }
            return list;
        }


        public int FindIndex(Predicate<T> match)
        {
            return FindIndex(0, _size, match);
        }


        public int FindIndex(int startIndex, Predicate<T> match)
        {
            return FindIndex(startIndex, _size - startIndex, match);
        }


        public int FindIndex(int startIndex, int count, Predicate<T> match)
        {
            if (startIndex > _size)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
            }
            if (count < 0 || startIndex > _size - count)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
            }
            if (match == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            int num = startIndex + count;
            for (int i = startIndex; i < num; i++)
            {
                if (match(Items[i]))
                {
                    return i;
                }
            }
            return -1;
        }


        public T FindLast(Predicate<T> match)
        {
            if (match == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            for (int i = _size - 1; i >= 0; i--)
            {
                if (match(Items[i]))
                {
                    return Items[i];
                }
            }
            return default;
        }


        public int FindLastIndex(Predicate<T> match)
        {
            return FindLastIndex(_size - 1, _size, match);
        }


        public int FindLastIndex(int startIndex, Predicate<T> match)
        {
            return FindLastIndex(startIndex, startIndex + 1, match);
        }


        public int FindLastIndex(int startIndex, int count, Predicate<T> match)
        {
            if (match == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            if (_size == 0)
            {
                if (startIndex != -1)
                {
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
                }
            }
            else if (startIndex >= _size)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
            }
            if (count < 0 || startIndex - count + 1 < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
            }
            int num = startIndex - count;
            for (int i = startIndex; i > num; i--)
            {
                if (match(Items[i]))
                {
                    return i;
                }
            }
            return -1;
        }


        public virtual void ForEach(Action<T> action)
        {
            int num = 0;
            while (num < _size)
            {
                action(Items[num]);
                num++;
            }
        }


        public Enumerator GetEnumerator()
        {
            return new Enumerator(this);
        }


        IEnumerator<T> IEnumerable<T>.GetEnumerator()
        {
            return new Enumerator(this);
        }


        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }


        public virtual T[] GetRange(int index, int count)
        {
            if (index < 0 || count < 0)
                return null;
            if (_size - index < count)
                count = _size - index;
            var list = new T[count];
            Array.Copy(Items, index, list, 0, count);
            return list;
        }

        /// <summary>
        /// 获取对象数组, 并移除对象数组, 如果长度大于列表的长度, 则会裁剪到能获取的长度
        /// </summary>
        /// <param name="index"></param>
        /// <param name="count"></param>
        /// <returns></returns>
        public virtual T[] GetRemoveRange(int index, int count)
        {
            if (_size - index < count)
                count = _size - index;
            if (count > 0)
            {
                _size -= count;
                var array = new T[count];
                Array.Copy(Items, index, array, 0, count);//复制移除的数组部分
                Array.Copy(Items, index + count, Items, index, _size - index);//将结尾数组移动到移除的数组部分来
                Array.Clear(Items, _size, count);
                return array;
            }
            return new T[0];
        }

        public int IndexOf(T item)
        {
            return Array.IndexOf(Items, item, 0, _size);
        }


        int IList.IndexOf(object item)
        {
            if (IsCompatibleObject(item))
                return IndexOf((T)item);
            return -1;
        }


        public int IndexOf(T item, int index)
        {
            if (index > _size)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
            }
            return Array.IndexOf(Items, item, index, _size - index);
        }


        public int IndexOf(T item, int index, int count)
        {
            if (index > _size)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
            }
            if (count < 0 || index > _size - count)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
            }
            return Array.IndexOf(Items, item, index, count);
        }


        public virtual void Insert(int index, T item)
        {
            if (index > _size)
                return;
            if (_size == Items.Length)
            {
                EnsureCapacity(_size + 1);
            }
            if (index < _size)
            {
                Array.Copy(Items, index, Items, index + 1, _size - index);
            }
            Items[index] = item;
            _size++;
        }

        void IList.Insert(int index, object item)
        {
            Insert(index, (T)item);
        }

        public virtual void InsertRange(int index, IEnumerable<T> collection)
        {
            if (collection == null)
                return;
            if (index > _size)
                return;
            if (collection is ICollection<T> collection2)
            {
                int count = collection2.Count;
                if (count > 0)
                {
                    EnsureCapacity(_size + count);
                    if (index < _size)
                    {
                        Array.Copy(Items, index, Items, index + count, _size - index);
                    }
                    if (this == collection2)
                    {
                        Array.Copy(Items, 0, Items, index, index);
                        Array.Copy(Items, index + count, Items, index * 2, _size - index);
                    }
                    else
                    {
                        T[] array = new T[count];
                        collection2.CopyTo(array, 0);
                        array.CopyTo(Items, index);
                    }
                    _size += count;
                }
            }
            else
            {
                foreach (T item in collection)
                {
                    Insert(index++, item);
                }
            }
        }

        public int LastIndexOf(T item)
        {
            if (_size == 0)
                return -1;
            return LastIndexOf(item, _size - 1, _size);
        }


        public int LastIndexOf(T item, int index)
        {
            if (index >= _size)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
            }
            return LastIndexOf(item, index, index + 1);
        }


        public int LastIndexOf(T item, int index, int count)
        {
            if (Count != 0 && index < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (Count != 0 && count < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (_size == 0)
            {
                return -1;
            }
            if (index >= _size)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
            }
            if (count > index + 1)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection);
            }
            return Array.LastIndexOf(Items, item, index, count);
        }


        public virtual bool Remove(T item)
        {
            int index = IndexOf(item);
            return RemoveAtInternal(index);
        }


        void IList.Remove(object item)
        {
            if (IsCompatibleObject(item))
                Remove((T)item);
        }


        public virtual int RemoveAll(Predicate<T> match)
        {
            int num = 0;
            while (num < _size && !match(Items[num]))
            {
                num++;
            }
            if (num >= _size)
            {
                return 0;
            }
            int i = num + 1;
            while (i < _size)
            {
                while (i < _size && match(Items[i]))
                {
                    i++;
                }
                if (i < _size)
                {
                    Items[num++] = Items[i++];
                }
            }
            Array.Clear(Items, num, _size - num);
            int result = _size - num;
            _size = num;
            return result;
        }


        public virtual void RemoveAt(int index)
        {
            RemoveAtInternal(index);
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        protected virtual bool RemoveAtInternal(int index)
        {
            if (index >= _size || index < 0)
                return false;
            _size--;
            if (index < _size)
                Items[index] = Items[_size];
            Items[_size] = default;
            return true;
        }


        public virtual void RemoveRange(int index, int count)
        {
            if (_size - index < count)
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
            if (count > 0)
            {
                _size -= count;
                if (index < _size)
                    Array.Copy(Items, index + count, Items, index, _size - index);
                Array.Clear(Items, _size, count);
            }
        }

        public virtual void Reverse()
        {
            Reverse(0, Count);
        }


        public virtual void Reverse(int index, int count)
        {
            if (index < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (count < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (_size - index < count)
            {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
            }
            Array.Reverse(Items, index, count);
        }


        public virtual void Sort()
        {
            Sort(0, Count, null);
        }


        public virtual void Sort(IComparer<T> comparer)
        {
            Sort(0, Count, comparer);
        }


        public virtual void Sort(int index, int count, IComparer<T> comparer)
        {
            if (index < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (count < 0)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            }
            if (_size - index < count)
            {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
            }
            Array.Sort(Items, index, count, comparer);
        }

        internal sealed class FunctorComparer<T1> : IComparer<T1>
        {
            private readonly Comparison<T1> comparison;

            public FunctorComparer(Comparison<T1> comparison)
            {
                this.comparison = comparison;
            }

            public int Compare(T1 x, T1 y)
            {
                return comparison(x, y);
            }
        }

        public virtual void Sort(Comparison<T> comparison)
        {
            if (comparison == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            if (_size > 0)
            {
                IComparer<T> comparer = new FunctorComparer<T>(comparison);
                Array.Sort(Items, 0, _size, comparer);
            }
        }


        public virtual T[] ToArray()
        {
            T[] array = new T[_size];
            Array.Copy(Items, 0, array, 0, _size);
            return array;
        }


        public void TrimExcess()
        {
            int num = (int)(Items.Length * 0.9);
            if (_size < num)
            {
                Capacity = _size;
            }
        }


        public bool TrueForAll(Predicate<T> match)
        {
            if (match == null)
            {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
            }
            for (int i = 0; i < _size; i++)
            {
                if (!match(Items[i]))
                {
                    return false;
                }
            }
            return true;
        }

        [Serializable]
        internal class SynchronizedList : IList<T>, ICollection<T>, IEnumerable<T>, IEnumerable
        {
            // 字段
            private readonly ListSafe<T> _list;
            private readonly object _root;

            // 属性
            public int Count => _list.Count;

            public bool IsReadOnly => ((ICollection<T>)_list).IsReadOnly;

            public T this[int index]
            {
                get
                {
                    object root = _root;
                    T result;
                    lock (root)
                    {
                        result = _list[index];
                    }
                    return result;
                }
                set
                {
                    object root = _root;
                    lock (root)
                    {
                        _list[index] = value;
                    }
                }
            }

            // 构造函数
            internal SynchronizedList(ListSafe<T> list)
            {
                _list = list;
                _root = ((ICollection)list).SyncRoot;
            }

            // 方法
            public void Add(T item)
            {
                object root = _root;
                lock (root)
                {
                    _list.Add(item);
                }
            }

            public void Clear()
            {
                object root = _root;
                lock (root)
                {
                    _list.Clear();
                }
            }

            public bool Contains(T item)
            {
                object root = _root;
                bool result;
                lock (root)
                {
                    result = _list.Contains(item);
                }
                return result;
            }

            public void CopyTo(T[] array, int arrayIndex)
            {
                object root = _root;
                lock (root)
                {
                    _list.CopyTo(array, arrayIndex);
                }
            }

            public bool Remove(T item)
            {
                object root = _root;
                bool result;
                lock (root)
                {
                    result = _list.Remove(item);
                }
                return result;
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                object root = _root;
                IEnumerator result;
                lock (root)
                {
                    result = _list.GetEnumerator();
                }
                return result;
            }

            IEnumerator<T> IEnumerable<T>.GetEnumerator()
            {
                object root = _root;
                IEnumerator<T> enumerator;
                lock (root)
                {
                    enumerator = ((IEnumerable<T>)_list).GetEnumerator();
                }
                return enumerator;
            }

            public int IndexOf(T item)
            {
                object root = _root;
                int result;
                lock (root)
                {
                    result = _list.IndexOf(item);
                }
                return result;
            }

            public void Insert(int index, T item)
            {
                object root = _root;
                lock (root)
                {
                    _list.Insert(index, item);
                }
            }

            public void RemoveAt(int index)
            {
                object root = _root;
                lock (root)
                {
                    _list.RemoveAt(index);
                }
            }
        }


        [Serializable]
        public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
        {
            // 字段
            private readonly FastList<T> list;
            private int index;
            private T current;

            // 属性
            public T Current => current;
            object IEnumerator.Current => Current;

            // 构造函数
            internal Enumerator(FastList<T> list)
            {
                this.list = list;
                index = 0;
                current = default;
            }

            // 方法
            public void Dispose()
            {
            }

            public bool MoveNext()
            {
                var list = this.list;
                if (index < list._size)
                {
                    current = list.Items[index];
                    index++;
                    return true;
                }
                return MoveNextRare();
            }

            private bool MoveNextRare()
            {
                index = list._size + 1;
                current = default;
                return false;
            }

            void IEnumerator.Reset()
            {
                index = 0;
                current = default;
            }
        }
    }
}